# LeetCode 450、删除二叉搜索树中的节点

# 一、题目描述

给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。

一般来说,删除节点可分为两个步骤:

1、首先找到需要删除的节点;

2、如果找到了,删除它。

# 二、题目解析

# 三、参考代码

# 1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 删除二叉搜索树中的节点( LeetCode 450 ):https://leetcode-cn.com/problems/delete-node-in-a-bst/
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {

        // 1、如果 root 为空,那么直接返回空
        if (root == null) return null;

        // 2、如果 root 的节点值等于需要删除的值,那么需要根据以下几种情况进行处理
        if (root.val == key) {
     
            // 情况 1:当前节点的左子树为空,那么当前节点 root 由 root 的右子树占位就行
            // 比如 key 为 7
            //       6
            //     /   \
            //    2     7
            //           \
            //            8
            // 直接将以 8 作为根节点的二叉树挪到 7 的位置
            //       6
            //     /   \
            //    2     8
            if (root.left == null) return root.right;

            // 情况 2:当前节点的右子树为空,那么当前节点 root 由 root 的左子树占位就行
            // 比如 key 为 2
            //       6
            //     /   \
            //    2     7
            //   /        
            //  1          
            // 直接将以 1 作为根节点的二叉树挪到 2 的位置
            //       6
            //     /   \
            //    1     7
            if (root.right == null) return root.left;

            // 情况 3:被删除节点既有左子树,又有右子树
            // 比如 key 为 2
            //          5
            //       /     \
            //      2       6
            //    /   \       \
            //   1     4       7
            //        /
            //       3
            // 需要找到右子树最小的值,或者左子树中最大的值
            // 这里我们去找右子树最小的值,为 3
            TreeNode minNodeOfRight = findMinNode(root.right);

            // 找到右子树最小的值之后,修改当前节点 root 的值为右子树最小的值
            root.val = minNodeOfRight.val;
            
            // 同时,记得删除掉 root 的右子树最小的值之
            // 删除操作就是以 root 作为根节点,key 为右子树最小的值进行删除
            root.right = deleteNode(root.right, minNodeOfRight.val);
          
          // 3、如果 root 的节点值小于需要删除的值,那么就在 root 的右子树中去查找
        } else if (root.val < key) {
            // 在 root 的右子树中去查找并删除 key 
            root.right = deleteNode(root.right, key);

          // 4、如果 root 的节点值大于需要删除的值,那么就在 root 的左子树中去查找
        } else if (root.val > key) {
            // 在 root 的左子树中去查找并删除 key 
            root.left = deleteNode(root.left, key);
        }

        // 最后返回需要已经删除了 key 的二叉树的根节点
        return root;
    }

    // 通过 findMinNode ,可以找到二叉搜索树中最小的元素
    private TreeNode findMinNode(TreeNode node) {

        // 由于二叉搜索树,左子树所有元素的值都小于根节点的值
        // 所以可以不断的查找,直到为叶子节点,那么就找到了
        while (node.left != null) {
            // 不断的去查找当前节点的左子树
            node = node.left;
        }

        // 返回当前二叉搜索树中最小的元素
        return node;
    }
}

# **2、**C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 删除二叉搜索树中的节点( LeetCode 450 ):https://leetcode-cn.com/problems/delete-node-in-a-bst/
class Solution
{
public:
    TreeNode *deleteNode(TreeNode *root, int key)
    {

        // 1、如果 root 为空,那么直接返回空
        if (root == NULL)
            return NULL;

        // 2、如果 root 的节点值等于需要删除的值,那么需要根据以下几种情况进行处理
        if (root->val == key)
        {

            // 情况 1:当前节点的左子树为空,那么当前节点 root 由 root 的右子树占位就行
            // 比如 key 为 7
            //       6
            //     /   \
            //    2     7
            //           \
            //            8
            // 直接将以 8 作为根节点的二叉树挪到 7 的位置
            //       6
            //     /   \
            //    2     8
            if (root->left == NULL)
                return root->right;

            // 情况 2:当前节点的右子树为空,那么当前节点 root 由 root 的左子树占位就行
            // 比如 key 为 2
            //       6
            //     /   \
            //    2     7
            //   /
            //  1
            // 直接将以 1 作为根节点的二叉树挪到 2 的位置
            //       6
            //     /   \
            //    1     7
            if (root->right == NULL)
                return root->left;

            // 情况 3:被删除节点既有左子树,又有右子树
            // 比如 key 为 2
            //          5
            //       /     \
            //      2       6
            //    /   \       \
            //   1     4       7
            //        /
            //       3
            // 需要找到右子树最小的值,或者左子树中最大的值
            // 这里我们去找右子树最小的值,为 3
            TreeNode *minNodeOfRight = findMinNode(root->right);

            // 找到右子树最小的值之后,修改当前节点 root 的值为右子树最小的值
            root->val = minNodeOfRight->val;

            // 同时,记得删除掉 root 的右子树最小的值之
            // 删除操作就是以 root 作为根节点,key 为右子树最小的值进行删除
            root->right = deleteNode(root->right, minNodeOfRight->val);

            // 3、如果 root 的节点值小于需要删除的值,那么就在 root 的右子树中去查找
        }
        else if (root->val < key)
        {
            // 在 root 的右子树中去查找并删除 key
            root->right = deleteNode(root->right, key);

            // 4、如果 root 的节点值大于需要删除的值,那么就在 root 的左子树中去查找
        }
        else if (root->val > key)
        {
            // 在 root 的左子树中去查找并删除 key
            root->left = deleteNode(root->left, key);
        }

        // 最后返回需要已经删除了 key 的二叉树的根节点
        return root;
    }

    // 通过 findMinNode ,可以找到二叉搜索树中最小的元素
    TreeNode *findMinNode(TreeNode *node)
    {

        // 由于二叉搜索树,左子树所有元素的值都小于根节点的值
        // 所以可以不断的查找,直到为叶子节点,那么就找到了
        while (node->left != NULL)
        {
            // 不断的去查找当前节点的左子树
            node = node->left;
        }

        // 返回当前二叉搜索树中最小的元素
        return node;
    }
};

# 3、Python 代码

登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者:程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 删除二叉搜索树中的节点( LeetCode 450 ):https://leetcode-cn.com/problems/delete-node-in-a-bst/
class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:

        # 1、如果 root 为空,那么直接返回空
        if not root :
          return None

        # 2、如果 root 的节点值等于需要删除的值,那么需要根据以下几种情况进行处理
        if root.val == key :
     
            # 情况 1:当前节点的左子树为空,那么当前节点 root 由 root 的右子树占位就行
            # 比如 key 为 7
            #       6
            #     /   \
            #    2     7
            #           \
            #            8
            # 直接将以 8 作为根节点的二叉树挪到 7 的位置
            #       6
            #     /   \
            #    2     8
            if not root.left:
               return root.right

            # 情况 2:当前节点的右子树为空,那么当前节点 root 由 root 的左子树占位就行
            # 比如 key 为 2
            #       6
            #     /   \
            #    2     7
            #   /        
            #  1          
            # 直接将以 1 作为根节点的二叉树挪到 2 的位置
            #       6
            #     /   \
            #    1     7
            if not root.right :
               return root.left

            # 情况 3:被删除节点既有左子树,又有右子树
            # 比如 key 为 2
            #          5
            #       /     \
            #      2       6
            #    /   \       \
            #   1     4       7
            #        /
            #       3
            # 需要找到右子树最小的值,或者左子树中最大的值
            # 这里我们去找右子树最小的值,为 3
            minNodeOfRight =  self.findMinNode(root.right)

            # 找到右子树最小的值之后,修改当前节点 root 的值为右子树最小的值
            root.val = minNodeOfRight.val
            
            # 同时,记得删除掉 root 的右子树最小的值之
            # 删除操作就是以 root 的右子树作为根节点,key 为右子树最小的值进行删除
            root.right =  self.deleteNode(root.right,minNodeOfRight.val)
          
          # 3、如果 root 的节点值小于需要删除的值,那么就在 root 的右子树中去查找
        elif root.val < key :
            # 在 root 的右子树中去查找并删除 key 
            root.right =  self.deleteNode(root.right,key)

          # 4、如果 root 的节点值大于需要删除的值,那么就在 root 的左子树中去查找
        elif root.val > key : 
            # 在 root 的左子树中去查找并删除 key 
            root.left = self.deleteNode(root.left,key)
        

        # 最后返回需要已经删除了 key 的二叉树的根节点
        return root
    

    # 通过 findMinNode ,可以找到二叉搜索树中最小的元素
    def findMinNode(self , node : TreeNode) -> TreeNode : 

        # 由于二叉搜索树,左子树所有元素的值都小于根节点的值
        # 所以可以不断的查找,直到为叶子节点,那么就找到了
        while node.left :
            # 不断的去查找当前节点的左子树
            node = node.left
        

        # 返回当前二叉搜索树中最小的元素
        return node